package com.lx.algorithm.code;

import com.lx.algorithm.Tree.Node;

import static com.lx.algorithm.Tree.FindFather.pickRandomOne;
import static com.lx.algorithm.Tree.TreeUtils.generateRandomBST;

/**
 * Description:
 * Copyright:   Copyright (c)2019
 * Company:     zefu
 *
 * @author: 张李鑫
 * @version: 1.0
 * Create at:   2021-12-30 15:48:08
 * <p>
 * Modification History:
 * Date         Author      Version     Description
 * ------------------------------------------------------------------
 * 2021-12-30     张李鑫                     1.0         1.0 Version
 */
public class Code07 {
    /**
     * 给定一个二叉树的头节点head，路径的规定有以下三种不同的规定：
     * <p>
     * 1）路径必须是头节点出发，到叶节点为止，返回最大路径和
     * <p>
     * 2）路径可以从任何节点出发，但必须往下走到达任何节点，返回最大路径和
     * <p>
     * 3）路径可以从任何节点出发，到任何节点，返回最大路径和
     */


    /**
     * 路径必须是头节点出发，到叶节点为止，返回最大路径和
     *
     * @param head
     * @return
     */
    public static int maxLength1(Node head) {
        return process1(head);
    }

    /**
     * 这里不能用 null做baseCase
     * -1
     * null  -5
     * 这样的树就会返回-1
     *
     * @param head
     * @return
     */
    private static int process1(Node head) {
        if (head.left == null && head.right == null) {
            return (int) head.value;
        }
        int next = Integer.MIN_VALUE;
        if (head.left != null) {
            next = Math.max(process1(head.left), next);
        }
        if (head.right != null) {
            next = Math.max(process1(head.right), next);
        }
        return next + (int) head.value;
    }

    public static Integer maxVal = Integer.MIN_VALUE;

    private static int process2(Node head) {

        if (head == null) {
            return 0;
        }
        int next = Integer.MIN_VALUE;
        next = Math.max(process2(head.left), next);
        next = Math.max(process2(head.right), next);
        //这里必须返回带头的信息 如果有最大的值记录在static 关键字里
        int res = Math.max(next + (int) head.value, (int) head.value);
        maxVal = Math.max(Math.max(next, res), (int) head.value);
        return res;
    }

    private static int process3(Node head) {

        if (head == null) {
            return 0;
        }
        int next = Integer.MIN_VALUE;
        int l = process3(head.left);
        int r = process3(head.right);
        maxVal = Math.max(l + r + ((int) (head.value)), maxVal);

        next = Math.max(l, next);
        next = Math.max(r, next);
        //这里必须返回带头的信息 如果有最大的值记录在static 关键字里
        int res = Math.max(next + (int) head.value, (int) head.value);
        maxVal = Math.max(Math.max(next, res), (int) head.value);
        return res;
    }

    public static class In {
        public int lMax;
        public int rMax;
        public int max;


        public In(int lMax, int rMax, int max) {
            this.lMax = lMax;
            this.rMax = rMax;
            this.max = max;
        }
    }

    public static Info f3(Node x) {
        if (x == null) {
            return null;
        }
        Info leftInfo = f3(x.left);
        Info rightInfo = f3(x.right);
        int p1 = Integer.MIN_VALUE;
        if (leftInfo != null) {
            p1 = leftInfo.allTreeMaxSum;
        }
        int p2 = Integer.MIN_VALUE;
        if (rightInfo != null) {
            p2 = rightInfo.allTreeMaxSum;
        }
        int p3 = (int) x.value;
        int p4 = Integer.MIN_VALUE;
        if (leftInfo != null) {
            p4 = (int) x.value + leftInfo.fromHeadMaxSum;
        }
        int p5 = Integer.MIN_VALUE;
        if (rightInfo != null) {
            p5 = (int) x.value + rightInfo.fromHeadMaxSum;
        }

        int p6 = Integer.MIN_VALUE;
        if (leftInfo != null && rightInfo != null) {
            p6 = (int) x.value + leftInfo.fromHeadMaxSum + rightInfo.fromHeadMaxSum;
        }

        int allTreeMaxSum = Math.max(Math.max(Math.max(p1, p2), p3), Math.max(Math.max(p4, p5), p6));
        int fromHeadMaxSum = Math.max(Math.max(p3, p4), p5);
        return new Info(allTreeMaxSum, fromHeadMaxSum);
    }

    public static Info f2(Node x) {
        if (x == null) {
            return null;
        }
        Info leftInfo = f2(x.left);
        Info rightInfo = f2(x.right);
        int p1 = Integer.MIN_VALUE;
        if (leftInfo != null) {
            p1 = leftInfo.allTreeMaxSum;
        }
        int p2 = Integer.MIN_VALUE;
        if (rightInfo != null) {
            p2 = rightInfo.allTreeMaxSum;
        }
        int p3 = (int) x.value;
        int p4 = Integer.MIN_VALUE;
        if (leftInfo != null) {
            p4 = (int) x.value + leftInfo.fromHeadMaxSum;
        }
        int p5 = Integer.MIN_VALUE;
        if (rightInfo != null) {
            p5 = (int) x.value + rightInfo.fromHeadMaxSum;
        }
        int allTreeMaxSum = Math.max(Math.max(Math.max(p1, p2), p3), Math.max(p4, p5));
        int fromHeadMaxSum = Math.max(Math.max(p3, p4), p5);
        return new Info(allTreeMaxSum, fromHeadMaxSum);
    }


    public static class Info {
        public int allTreeMaxSum;
        public int fromHeadMaxSum;

        public Info(int all, int from) {
            allTreeMaxSum = all;
            fromHeadMaxSum = from;
        }
    }

    public static boolean maxLength2(Node head) {
        if (head == null) {
            return true;
        }
        int f = f2(head).fromHeadMaxSum;
        int p = process2(head);
        if (f != p) {
            System.out.print(f + "," + p);
            return false;
        }
        return true;
    }

    public static void main(String[] args) {

        int maxLevel = 10;
        int maxValue = 100;
        int testTimes = 1000000;
        for (int i = 0; i < testTimes; i++) {
            Node head = generateRandomBST(maxLevel, maxValue);
            maxVal = Integer.MIN_VALUE;
            if (head == null) {
                continue;
            }
            Info info = f3(head);
            process3(head);
            if (maxVal != info.fromHeadMaxSum) {
                System.out.println(info.fromHeadMaxSum);
                System.out.println(info.allTreeMaxSum);
                System.out.println(maxVal);
                break;
            }
        }
        System.out.println("finish!");
    }
}
